package test.algorithm.FastSlowPointer;

import java.util.ArrayList;
import java.util.List;

/**
 * 快慢指针
 * (在不知道链表长度的情况下，快速查找中间节点的值)
 * (判断是否循环链表，快指针是否和慢指针指向同一个对象。即快指针比满指针赶上了慢指针，可认为有循环)
 * @author serenity
 *
 */
public class FastSlowPointer {

	public static void main(String[] args) {
		
		List<Integer> list = new ArrayList<Integer>();
		
		// 初始化链表
		for(int i=0;i<10;i++){
			list.add(i);
		}
		
		// 初始化快慢指针（都指向数组第一个元素）
		int fast,slow;
		fast = slow = 0;
		
		try{
			while(list.get(fast)!=null){
				// 快指针步进
				fast = fast+2;
				
				// 慢指针步进
				slow = slow+1;
			}
		}catch(IndexOutOfBoundsException e){
			// 最后一次指针移动已越界，回退
			fast = fast-2;
			slow = slow-1;
			
			System.out.print("链表：");
			for(Integer i:list){
				System.out.print(list.get(i)+"  ");
			}
			
			System.out.println();
			
			// 打印中间节点值
			System.out.print("中间节点值：");
			System.out.print(list.get(slow));
		}
		
		
		
		
		
	}

}
